//给定一个二叉树，返回它的 后序 遍历。 
//
// 示例: 
//
// 输入: [1,null,2,3]  
//   1
//    \
//     2
//    /
//   3 
//
//输出: [3,2,1] 
//
// 进阶: 递归算法很简单，你可以通过迭代算法完成吗？ 
// Related Topics 栈 树 
// 👍 346 👎 0

package leetcode.editor.cn;

import leetcode.editor.commons.TreeNode;

import java.sql.Statement;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

//Java：二叉树的后序遍历
public class P145BinaryTreePostorderTraversal {
    public static void main(String[] args) {
        Solution solution = new P145BinaryTreePostorderTraversal().new Solution();
        // TO TEST
    }
    //leetcode submit region begin(Prohibit modification and deletion)



    /*
    二叉树的后序遍历
    * */
    class Solution {
        /*
        使用递归的写法
        * */
        private List<Integer> list=new ArrayList<>();
        public List<Integer> postorderTraversal1(TreeNode root) {
            if(root==null){
                return list;
            }
            //左 右  根
            postorderTraversal1(root.left);
            postorderTraversal1(root.right);
            list.add(root.val);
            return list;
        }

        /*
        按照题目要求，写非递归的写法
        * */

        public List<Integer> postorderTraversal(TreeNode root) {
            List<Integer> res=new ArrayList<>();
            if(root==null){
                return res;
            }

            Stack<TreeNode> stack=new Stack<>();
            stack.push(root);
            while (!stack.isEmpty()){
                TreeNode node=stack.pop();
                if(node!=null){//左->右->根=====>进栈顺序  根->右->左
                    stack.push(node);
                    stack.push(null);//用来记录已访问过
                    if(node.right!=null){
                        stack.push(node.right);
                    }
                    if(node.left!=null){
                        stack.push(node.left);
                    }
                }else{
                    res.add(stack.pop().val);
                }
            }

            return res;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}
